2020 百度之星程序设计大赛 - 复赛

比赛

A

A 变化的期望就是 (m - B 攻击成功的期望次数)，挺简单的一题

B

题目读错了（这也能错？）我看成在任意位置加一了就不会做啊啊啊

操作二只会执行一次或不执行，因为把前面一串清零了还要变成 1 才能再做操作二，目的仅仅为了将后面一位变成 1，这显然用操作一就够了。。枚举操作二把多长的前缀变成 0 就好了。

C

小构造题。最小和最大是相似的情况，这里就考虑最大的。考虑我们想要大的数贡献尽量大，可以这样构造：l = 8, k = 3，000001110000011100000111… 从大到小依次给 1 赋值。

D

咕咕

E

攻击总共有四种情况，其中如果同一轮中两个人都 miss 了相当于没有贡献，具体来说

设 $f(n, m)$ 为从 (n, m) 出发，Alice 活下来的概率。那么

$f(n, m) = f(n, m)(1 - p)(1 - q) + f(n, m - 1)p(1 - q) + f(n - 1, m)q(1 - p) + f(n - 1, m - 1)pq$

$f(n, m) = \frac{f(n, m - 1)p(1 - q) + f(n - 1, m)q(1 - p) + f(n - 1, m - 1)pq}{1 - (1 - p)(1 - q)}$

可以看作

  • case 1: $(n, m)$ 有 $a = \frac{pq}{1 - (1 - p)(1 - q)}$ 的概率转到 $(n - 1, m - 1)$
  • case 2: 有 $b = \frac{p(1 - q)}{1 - (1 - p)(1 - q)}$ 的概率转到 $(n, m - 1)$
  • case 3: 有 $c = \frac{q(1 - p)}{1 - (1 - p)(1 - q)}$ 的概率转到 $(n - 1, m)$

设最终移动到了 $(r, 1)$ (为什么不是 $(r, 0)$？因为最后一次 Alice 把 Bob 打死，Bob 没有机会攻击 Alice) ，case 1 操作了 $x$ 次，那么 case 2 操作了 $m - 1 - x$ 次，case 3 操作了 $n - r - x$ 次，就可以写出柿子：

$\sum\limits_{r = 1}^n \sum\limits_{x = 0}^{min(n - r, m - 1)} C(m - 1, x) \times C(m - 1 + n - r - x, m - 1) \times a^x b^{m - 1 - x} c^{n - r - x}$

这个不好搞，继续推，设 i = n - r - x

$\sum\limits_{x = 0}^{min(n - 1, m - 1)} a^xb^{m - 1 - x} C(m - 1, x) \sum\limits_{i = 0}^{n - 1 - x} C(m - 1 + i, i) c^i$

其中后面那个 sigma 可以前缀和预处理。

F

咕咕